package com.freedy.algorithm.prim;

/**
 * 创建最小生成树->村庄的图
 *
 * @author Freedy
 * @date 2021/4/13 21:58
 */
public class MinTree {
    private MGraph graph;

    public MinTree(MGraph graph) {
        this.graph = graph;
    }

    public void createMinTree() {
        System.out.println("生成最小生成树");
        int[] visited = new int[graph.verxs];//标记节点是否被访问
        visited[0] = 1;
        int index1 = -1, index2 = -1;//记录最小距离两点的下标
        int minWeight ;//两点间的最小距离
        for (int i = 1; i < graph.verxs; i++) {//有verxs个点->最小生成树有verxs-1条边
            minWeight=Integer.MAX_VALUE;//每次循环重置minWeight
            //确定每一次生成的子图，和哪个节点的距离最近
            for (int j = 0; j < graph.verxs; j++) {
                for (int k = 0; k < graph.verxs; k++) {
                    if (visited[j] == 1 &&
                            visited[k] == 0 &&
                            graph.weight[j][k] < minWeight &&
                            graph.weight[j][k] != 0) {//0代表无穷远或者无穷近
                        minWeight=graph.weight[j][k];
                        index1=j;
                        index2=k;
                    }
                }
            }
            visited[index2]=1;
            System.out.println(graph.data[index1]+"->"+graph.data[index2]+" 距离:"+graph.weight[index1][index2]);
        }
    }
}
